package leetcode100

// TODO 前序遍历 【-】 二叉树展开为链表
// TODO https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/

func flatten(root *TreeNode)  {
    res := []*TreeNode{}   // 用于保存遍历结果, 并不算严格意义上的 队列
	preDfs(root, &res)

    for i := 1; i < len(res); i++ {
        prev, curr := res[i-1], res[i]
        prev.Left, prev.Right = nil, curr
    }
}

// 前序遍历
func preDfs(root *TreeNode, res *[]*TreeNode) {
	if root == nil {
		return
	}
	*res = append(*res, root)
    preDfs(root.Left, res)
	preDfs(root.Right, res)
}